#lang racket
;Insertion-sort(Сортировка вставками)
(define (insertion-sort lst)
    (cond
        [(empty? lst) lst] 
        (else
            (insert (car lst) (insertion-sort (cdr lst))) )))

(define (insert n lst)
    (cond
        [(empty? lst) (cons n lst)] 
        [(<= n (car lst)) (cons n lst)] 
        (else 
            (cons (car lst) (insert n (cdr lst))) )))
;(insertion-sort '(5 1 3))
; is-> 5 1 3
;     c2: i-> 5, is -> 1 3
;                     c2: i -> 1, is -> 3
;                                      c2: i -> 3, is -> ()
;                                                  c1: <- ()
;                                      c2: i -> 3, ()
;                                               c1: <- (3)
;                     c2: i -> 1, (3)
;                   c1: <- (1 3)
;     c2: i -> 5, (1 3)
;             c3: <- 1, i -> 5, (3)
;                            c3: <- (3, i -> 5, ())
;                                            c1: <- (5)
;     c2: (1 3 5)
; is <- (1 3 5)